﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Graph
{
    class UndirectedGraph : BaseGraph
    {
        public class UndirectedCycle : Cycle
        {
            public UndirectedCycle(int begin, LinkedList<int> vertexes) : base(begin, vertexes) { }

            protected override Direction ChooseDirection(int indexMin)
            {
                int indexLeft = indexMin == 0 ? Vertexes.Count : indexMin - 1;
                int indexRight = indexMin == Vertexes.Count - 1 ? 0 : indexMin + 1;
                if (Vertexes.Count > 2 && Vertexes[indexLeft] < Vertexes[indexRight])
                    return Direction.LEFT;
                return Direction.RIGHT;
            }
        }

        public UndirectedGraph(string filePath) : base(filePath) { }

        protected override void addToAdjMatrix(Vertex v1, Vertex v2)
        {
            adjMatrix[v1.Key, v2.Key] = 1;
            if (v1.Key != v2.Key)
                adjMatrix[v2.Key, v1.Key] = 1;
        }

        //find all cycles by DFS
        protected override void DFS(Vertex begin)
        {
            DFSVisit(begin);
            foreach (KeyValuePair<string, Vertex> vertex in vertexs)
            {
                if (vertex.Value.Color == VertexColor.WHITE && vertex.Value.Key != begin.Key)
                {
                    DFSVisit(vertex.Value);
                }
            }
        }

        private void DFSVisit(Vertex v)
        {
            v.Color = VertexColor.GRAY;
            time++;
            v.D = time;
            List<Vertex> adjVertes = this.getAdjOfVertex(v);
            foreach (Vertex u in adjVertes)
            {
                if (u.equal(v.Father))
                {
                    continue; // not check
                }
                if (u.Color == VertexColor.WHITE)
                {
                    u.Father = v;
                    DFSVisit(u);
                }
                else if (u.Color == VertexColor.GRAY && v != u)
                { // have cycles, tracking it
                    Cycle acycle = trackCycle(v, u);
                    addIfAbsent(acycle);
                }
            }
            v.Color = VertexColor.BLACK;
            time++;
            v.F = time;
        }

        private void addIfAbsent(Cycle acycle)
        {
            if (acycle == null) return;
            foreach (Cycle cycle in cycles)
                if (CycleCmper.Equals(cycle, acycle)) return;
            this.cycles.Add(acycle);
        }

        protected override BaseGraph.Cycle NewCycle(int begin, LinkedList<int> vertexes)
        {
            return new UndirectedCycle(begin, vertexes);
        }
    }
}
